package com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组;

/**
 *  5,最长回文子串
 *   中心扩散法 解决
 *   @see com.arron.algorithm.leetcodetop100.双指针.最长回文子串
 */
public class 最长回文子串 {


    // f(i,j)  表示字符串i到j是否是回文字符串
    // f(i,j) = f(i-1,j-1) && s[i] == s[j] 如果整个字符串是回文字符串
    //  则 f(i_+1,j-1) ==true ，且 s[i]== s[j]
    public String longestPalindrome(String s) {

        int length = s.length();
        boolean[][] dp= new boolean[length][length];
        for (int i = 0; i < length; i++) {
            //每个字符单独都是回文字符
            dp[i][i] = true;
        }
        //长度至少为1，单独每个字符串都是一个回文字符
        int maxLen = 1;
        int maxStartIndex = 0;
        //穷举 长度为2 开始的字符串
        for (int l = 2; l <= length; l++) {

            for (int i = 0; i < length; i++) {

                int j = l+i-1;
                //这里已经控制了 i+1 <length
                if (j>=length){
                    break;
                }
                if (s.charAt(i) !=s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    if (j-i <3){

                        dp[i][j] = true;
                    }else {
                        //这里j 能取到的最小值为 1，因此j-1始终 >= 0
                        dp[i][j] = dp[i+1][j-1];
                    }


                }


                if (dp[i][j]){
                    maxLen = Math.max(l,maxLen);
                    maxStartIndex = l ==maxLen?i:maxStartIndex;
                }
            }
        }

        return s.substring(maxStartIndex,maxStartIndex+maxLen);
    }

    public static void main(String[] args) {
        String s = "cbbd";


        最长回文子串 longestPalindrome = new 最长回文子串();
        longestPalindrome.longestPalindrome(s);
    }


}
